/*
https://leetcode-cn.com/problems/minimum-cost-to-merge-stones/solution/c-acde-di-1000ti-xian-gei-di-1000ti-jing-ecs9/
 */
public class Solution1000 {
    public int mergeStones(int[] stones, int k) {
        int n=stones.length;
        if ((n-1)%(k-1)!=0){
            return -1;
        }
        int[] sum=new int[n+1];
        for (int i=1;i<=n;i++){
            sum[i]=sum[i-1]+stones[i-1];
        }
        int[][][] f=new int[n][n][k+1];
        for (int i=0;i<n;i++){
            for (int j=0;j<n;j++){
                for (int p=0;p<=k;p++){
                    f[i][j][p]=Integer.MAX_VALUE/3;
                }
            }
        }
        for (int i=0;i<n;i++){
            f[i][i][1]=0;
        }
        for (int len=2;len<=n;len++){
            for (int i=0;i<=n-len;i++){
                int j=i+len-1;
                for (int p=2;p<=k;p++){
                    for (int m=i;m<j;m=m+k-1){
                        f[i][j][p]=Math.min(f[i][j][p],f[i][m][1]+f[m+1][j][p-1]);
                    }
                }
                f[i][j][1]=f[i][j][k]+sum[j+1]-sum[i];
            }
        }
        return f[0][n-1][1];
    }

    public static void main(String[] args) {
        System.out.println(new Solution1000().mergeStones(new int[]{3,2,4,1},2));
    }
}
